package com.success.toutiao;

import org.junit.Test;

import java.util.Stack;

/**
 * Desc: 2018.11.28
 * 头条面试，提供笔记本，编程3选1，第三题
 * leetcode：https://leetcode.com/problems/add-two-numbers-ii/
 * Create by John Jiang On 2018/12/19
 */
public class AddTwoNumbersLinkedList {

    static class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        Stack<ListNode> s1 = new Stack<ListNode>();
        Stack<ListNode> s2 = new Stack<ListNode>();
        while (l1 != null) {
            s1.push(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2);
            l2 = l2.next;
        }
        Stack<ListNode> s3 = new Stack<ListNode>();
        int flag = 0;
        while (!s1.empty() && !s2.empty()) {
            int v1 = s1.pop().val;
            int v2 = s2.pop().val;
            int v3 = v1 + v2 + flag;
            if (v3 >= 10) {
                flag = 1;
                v3 = v3 - 10;
            } else {
                flag = 0;
            }
            s3.push(new ListNode(v3));
        }
        while (!s1.empty()) {
            int v1 = s1.pop().val;
            int v3 = v1 + flag;
            if (v3 >= 10) {
                flag = 1;
                v3 = v3 - 10;
            } else {
                flag = 0;
            }
            s3.push(new ListNode(v3));
        }
        while (!s2.empty()) {
            int v2 = s2.pop().val;
            int v3 = v2 + flag;
            if (v3 >= 10) {
                flag = 1;
                v3 = v3 - 10;
            } else {
                flag = 0;
            }
            s3.push(new ListNode(v3));
        }
        if (flag == 1) {
            s3.push(new ListNode(1));
        }
        ListNode head = s3.pop();
        ListNode tmp = head;
        while (!s3.empty()) {
            tmp.next = s3.pop();
            tmp = tmp.next;
        }
        return head;
    }

    @Test
    public void test() {
        ListNode l11 = new ListNode(5);
        ListNode l12 = new ListNode(4);
        ListNode l13 = new ListNode(3);
        ListNode l14 = new ListNode(2);
        ListNode l15 = new ListNode(1);
        l11.next = l12;
        l12.next = l13;
        l13.next = l14;
        l14.next = l15;
        ListNode l21 = new ListNode(5);
        ListNode l22 = new ListNode(4);
        ListNode l23 = new ListNode(3);
        ListNode l24 = new ListNode(2);
        ListNode l25 = new ListNode(1);
        l21.next = l22;
        l22.next = l23;
        l23.next = l24;
        l24.next = l25;
        ListNode result = addTwoNumbers(l11, l21);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }
}
